class Solution {
public:
    vector<int> sortArrayByParityII(vector<int>& nums) {
        int even = 0, odd = 1;
        int n = nums.size();
        for (int p = n - 1; even < n && odd < n; )
        {
            if ((nums[p] & 1) == 0)
            {
                swap(nums[even], nums[p]);
                even += 2;
                continue;
            }
            if (nums[p] & 1)
            {
                swap(nums[odd], nums[p]);
                odd += 2;
            }
        }
        return nums;
    }
};